Search results for "Computation Theory & Mathematics"
showing 10 items of 332 documents
The Average State Complexity of the Star of a Finite Set of Words Is Linear
2008
We prove that, for the uniform distribution over all sets Xof m(that is a fixed integer) non-empty words whose sum of lengths is n, $\mathcal{D}_X$, one of the usual deterministic automata recognizing X*, has on average $\mathcal{O}(n)$ states and that the average state complexity of X*is i¾?(n). We also show that the average time complexity of the computation of the automaton $\mathcal{D}_X$ is $\mathcal{O}(n\log n)$, when the alphabet is of size at least three.
Text Compression Using Antidictionaries
1999
International audience; We give a new text compression scheme based on Forbidden Words ("antidictionary"). We prove that our algorithms attain the entropy for balanced binary sources. They run in linear time. Moreover, one of the main advantages of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and allows parallel compression. Our algorithms can also be presented as "compilers" that create compressors dedicated to any previously fixed source. The techniques used in this paper are from Information Theory and Finite Automata.
Binary jumbled string matching for highly run-length compressible texts
2012
The Binary Jumbled String Matching problem is defined as: Given a string $s$ over $\{a,b\}$ of length $n$ and a query $(x,y)$, with $x,y$ non-negative integers, decide whether $s$ has a substring $t$ with exactly $x$ $a$'s and $y$ $b$'s. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time $O(n^2/\log n)$ [Burcsi et al., FUN 2010; Moosa and Rahman, IPL 2010], or $O(n^2/\log^2 n)$ in the word-RAM model [Moosa and Rahman, JDA 2012]. We propose an index constructed directly from the run-length encoding of $s$. The construction time of our index i…
A Motzkin filter in the Tamari lattice
2015
The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…
IRREDUCIBLE COXETER GROUPS
2004
We prove that a non-spherical irreducible Coxeter group is (directly) indecomposable and that an indefinite irreducible Coxeter group is strongly indecomposable in the sense that all its finite index subgroups are (directly) indecomposable. Let W be a Coxeter group. Write W = WX1 × ⋯ × WXb × WZ3, where WX1, … , WXb are non-spherical irreducible Coxeter groups and WZ3 is a finite one. By a classical result, known as the Krull–Remak–Schmidt theorem, the group WZ3 has a decomposition WZ3 = H1 × ⋯ × Hq as a direct product of indecomposable groups, which is unique up to a central automorphism and a permutation of the factors. Now, W = WX1 × ⋯ × WXb × H1 × ⋯ × Hq is a decomposition of W as a dir…
Fast Algorithms for Pseudoarboricity
2015
The densest subgraph problem, which asks for a subgraph with the maximum edges-to-vertices ratio d∗, is solvable in polynomial time. We discuss algorithms for this problem and the computation of a graph orientation with the lowest maximum indegree, which is equal to ⌈d∗⌉. This value also equals the pseudoarboricity of the graph. We show that it can be computed in O(|E| √ log log d∗) time, and that better estimates can be given for graph classes where d∗ satisfies certain asymptotic bounds. These runtimes are achieved by accelerating a binary search with an approximation scheme, and a runtime analysis of Dinitz’s algorithm on flow networks where all arcs, except the source and sink arcs, hav…
Self-stabilizing Balls & Bins in Batches
2016
A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast…
Periodicity, morphisms, and matrices
2003
In 1965, Fine and Wilf proved the following theorem: if (fn)n≥0 and (gn)n≥0 are periodic sequences of real numbers, of period lengths h and k, respectively, and fn = gn for 0 ≤ n > h + k - gcd(h,k), then fn = gn for all n ≥ 0. Furthermore, the constant h + k - gcd(h,k) is best possible. In this paper, we consider some variations on this theorem. In particular, we study the case where fn ≤ gn, instead of fn = gn. We also obtain generalizations to more than two periods.We apply our methods to a previously unsolved conjecture on iterated morphisms, the decreasing length conjecture: if h : Σ* → Σ* is a morphism with |Σ|= n, and w is a word with |w| < |h(w)| < |h2(w)| < ... < |hk(w)|, then k ≤ n.
A permutation code preserving a double Eulerian bistatistic
2016
Visontai conjectured in 2013 that the joint distribution of ascent and distinct nonzero value numbers on the set of subexcedant sequences is the same as that of descent and inverse descent numbers on the set of permutations. This conjecture has been proved by Aas in 2014, and the generating function of the corresponding bistatistics is the double Eulerian polynomial. Among the techniques used by Aas are the M\"obius inversion formula and isomorphism of labeled rooted trees. In this paper we define a permutation code (that is, a bijection between permutations and subexcedant sequences) and show the more general result that two $5$-tuples of set-valued statistics on the set of permutations an…
Alignment-free sequence comparison using absent words
2018
Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not oc…